The present invention relates to adders in general and in particular to one""s complement adders built from two""s complement adders.
Two""s complement adders and one""s complement adders are circuits used to add binary numbers, typically adding two binary numbers at a time. The operation of such adders is essentially the same for different sizes of binary numbers, but the addends and the sums are normally all represented by the same number of bits.
Binary addition (one""s complement and two""s complement) can be explained with a few simple examples. Suppose the two four-bit binary numbers 0011 and 0110 are being added. With two""s complement addition, the sum of these two numbers is 1001. Two""s complement addition corresponds well to the grade school notion of addition, in that 0011 and 0110 are binary representations of 3 and 6, respectively, and 1001 is the binary representation of 9, which is the sum of 3 and 6. Where N-bit binary numbers are being added and the sum is greater than 2Nxe2x88x921, a carry results. For example, 1001 and 1000 sum to 0001 and a carry (the carry bit representing in xe2x80x9c1xe2x80x9d in the 16""s column). With one""s complement addition, the carries are added back to the result. Thus, the one""s complement sum of 0011 and 0110 is 1001 (as with two""s complement addition), but the one""s complement sum of 1001 and 1000 is 0010.
Two""s complement adders are much more prevalent than one""s complement adders because two""s complement addition is used more. As standard cell logic developed, many cell developers refined and optimized two""s complement adder cells. Cells are preconfigured and pre-tested logic components for a particular process technology, usually a discrete logic technology or a semiconductor technology such as ECL or CMOS. While many two""s complement adders have been developed for use in various process technologies, one""s complement adders are not typically developed. Instead, one""s complement adders are formed from two""s complement adders.
One common and simple approach to creating an one""s complement adder out of a two""s complement adder is to start with a standard two""s complement adder and connect the carry output of the two""s complement adder to the carry input of the two""s complement adder to effect the one""s complement addition. Thus, the addends are added and, if the result of that addition generated a carry, the carry input is added to the result. This two-step process is a well-known approach to making a one""s complement adder out of a two""s complement adder. An example of such a one""s complement adder is shown in FIG. 1. There, a two""s complement adder 10 is configured to be a one""s complement adder by coupling the carry output of two""s complement adder 10 (COUT) to the carry input of two""s complement adder 10 (CIN). Thus, when two N-bit addends, A and B, are applied to the addend inputs of two""s complement adder 10 (IN1 and IN2), the resulting N-bit output, R, is provided at the output of two""s complement adder 10 (OUT), where R=A+B, with xe2x80x9c+xe2x80x9d representing the N-bit one""s complement addition operation.
Of course, the circuit must take into account that the two addends must be added together and the sum generated before the carry input is taken into account. Otherwise, a race condition might occur. One solution to the race problem is proposed in U.S. Pat. No. 4,298,952. As shown in that patent, the carry output can be conditioned into a generate signal G that is coupled to the carry input instead of the carry output.
While the conventional uses of two""s complement adders to form one""s complement adders work well in practice, they are often too slow for some applications. While changing to faster process technologies might increase the speed of a circuit, a better result is usually had by reducing the number of logic cycles needed for a given operation.
The problems of the prior art described above are overcome by the present invention. A one""s complement adder according to one embodiment of the present invention uses two two""s complement adders. Both of the two""s complement adders are coupled to receive first and second addends at their addend inputs, however the first two""s complement adder is adapted to output a first sum that is the one""s complement sum that would result if no carry occurred upon addition of the first and second addends and the second two""s complement adder is adapted to output a second sum that is the one""s complement sum that would result if a carry did occur. A selector selects one of the first sum and the second sum as its output (and the output of the one""s complement adder) based on whether or not a carry occurred.
In a particular embodiment, the indication of whether or not a carry occurred or not is determined from the carry output of the first complement adder. In a specific embodiment, the first sum is effected by setting the carry input for the first two""s complement adder to xe2x80x9c0xe2x80x9d (no carry in), the second sum is effected by setting the carry input for the second two""s complement adder to xe2x80x9c1xe2x80x9d (carry in) and the selector is a multiplexer with a select input coupled to the carry output of the first two""s complement adder.
One advantage of such a one""s complement adder is that the addition occurs in one pass instead of the passes of the conventional one""s complement adder.